package leecode.二叉树;

import java.util.ArrayList;
import java.util.List;

/**
 * @author wangxi created on 2021/6/6 17:47
 * @version v1.0
 *
 * 来自于 nowcoder
 *
 * 一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，
 * 使得这棵二叉树不再是搜索二叉树，请按升序输出这两个错误节点的值。(每个节点的值各不相同)
 *
 */
public class FindErrorNode {
    /**
     *
     * @param root TreeNode类 the root
     * @return int整型一维数组
     */
    public int[] findError (TreeNode root) {
        // write code here
        if (root == null) {
            return new int[0];
        }
        List<Integer> list = new ArrayList<>();
        help(list, root);
        int[] res = new int[2];
        for (int i = 0; i < list.size() - 1; i++) {
            int first = list.get(i);
            int second = list.get(i + 1);
            if (first > second) {
                res[1] = first;
                // 注意找到一个，就要退出，否则会和 第二个数有冲突
                break;
            }
        }
        for (int i = list.size() - 1; i > 0; i--) {
            int first = list.get(i);
            int second = list.get(i - 1);
            if (first < second) {
                res[0] = first;
                // 退出的原理与上面相同
                break;
            }
        }
        return res;
    }

    private void help(List<Integer> list, TreeNode root) {
        if (root == null) {
            return;
        }
        help(list, root.left);
        list.add(root.val);
        help(list, root.right);
    }
}
